package Test;

import java.util.Comparator;
import java.util.PriorityQueue;

public class 合并K个升序链表 {
    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode mergeKLists(ListNode[] lists) {
      ListNode dummy=new ListNode(-1);
      ListNode p=dummy;
      PriorityQueue<ListNode> pq=new PriorityQueue<>(lists.length,(a,b)->(a.val-b.val));
      for (ListNode node:lists){
          pq.add(node);
      }
      while (!pq.isEmpty()){
          ListNode node=pq.poll();
          if(node.next!=null){
              pq.add(node.next);
          }
          p.next=node;
          p=p.next;
      }
      return dummy.next;
    }
}
